
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.Random;

public class IDAStarSolutionFinder implements SolutionFinder 
{

	private volatile boolean finished = false;
	private volatile String solution = "";
	
//	private HashMap<Integer,VisitedEntry> visitedMap;
	
	private volatile Object finishedLock = new Object();

	MoveRule naiveMoveRule;
	
//	HashSet<Integer> visitedSet = new HashSet<Integer>();
	
	Random random = new Random();
	
	
	private static int iterationCounter = 0;
	
	private static MoveRule playeMoveRule = new PlayerMove();
	static DistanceCache distanceCache;
//	private static MoveRule boxMoveRule = new BoxMove();
	
//	private static final int DEPTH_PER_ITERATION = Integer.MAX_VALUE-10;
//	private static final int DEPTH_PER_ITERATION = 12;
	
	@Override
	public String FindSolution(Board board) 
	{
		board.printBoard();
		
		System.out.println("boxes = "+board.getBoxes().length);
		
		distanceCache = new DistanceCacheMegaMatrix( (BoardImplFast) board );
//		distanceCache = new ManhattanDistanceCache( (BoardImplFast) board );
		
		long before = System.currentTimeMillis();
		
//		boolean[][] deadlocks = AndraDeadlockArray.create( board );
//		boolean[][] deadlocks = CreateDeadLockArray.create( board );
//		
//		AndraDeadlockArray.printBoolocks( deadlocks );
		
		
		
		naiveMoveRule = new NaiveMoveWithDeadlocks( ((BoardImplFast)board).getDeadlockArray() );
//		naiveMoveRule = new NaiveMove();

//		Board originalBoard = board.clone();
		
//		for ( int depth = DEPTH_PER_ITERATION; 
//				depth < Integer.MAX_VALUE;
//				depth = depth + DEPTH_PER_ITERATION )
//		{
//			AStarSearch( board.clone(), depth);
//			AStarSearch( board.clone() );
			
//			System.out.println("IDA-depth = "+depth);
			
//			if ( finished )
//			{
//				break;
//			}
//		}
//		AStarSearch( board );
		
		
//		visitedMap = new HashMap<Integer,VisitedEntry>();
		
		SearchThread thread = new SearchThread( (BoardImplFast) board.clone() );
		thread.run();
		
		synchronized( finishedLock )
		{
			if ( !finished )
			{
				try 
				{
					finishedLock.wait();
				} 
				catch (InterruptedException e) 
				{
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			}
		}
		
		
//		SolutionConfirmer.confirm(board, solution);
		

		System.out.println( "Time = " + (System.currentTimeMillis()-before) );
		System.out.println("iterationCounter = "+iterationCounter);
		
		
		return solution;
	}
	
	private class SearchThread extends Thread
	{
		
		BoardImplFast board;
		
		public SearchThread( BoardImplFast board )
		{
			this.board = board;
		}
		
		@Override
		public void run()
		{
			AStarSearch( board );
		}
	}
	
	private void reportSolution( String solution )
	{
		synchronized( finishedLock )
		{
			finished = true;
			
			finishedLock.notifyAll();
		}
	}
	
//	public void AStarSearch( Board oldBoard, int maxDepth )
	public void AStarSearch( BoardImplFast oldBoard )
	{
		
		HashMap<Integer,VisitedEntry> visitedMap = new HashMap<Integer,VisitedEntry>();
		PriorityQueue<BoardPath> queue = new PriorityQueue<BoardPath>();
		
//		int[][] boxManhattanDistanceMatrix = new int[ ((BoardImplFast)oldBoard).getXLength() ][ ((BoardImplFast)oldBoard).getYLength() ];
		
		Cord[] goals = oldBoard.getGoals();
	
		
		VisitedEntry entry = new VisitedEntry( oldBoard.hashCode(), null, null );
		
		visitedMap.put( oldBoard.hashCode() , entry);

//		queue.add( new BoardPath( oldBoard, "", 0, BoardPath.BeginDirection.Forward, boxManhattanDistanceMatrix, null, distanceCache ) );
		queue.add( new BoardPath( oldBoard, "", 0, BoardPath.BeginDirection.Forward, null, distanceCache ) );
		
		while ( !queue.isEmpty() )
		{

			BoardPath boardPath = queue.remove();
			
			AStarSearch( boardPath, queue, visitedMap );
						
		}
		
	}
		
	
	private void AStarSearch ( BoardPath bp, PriorityQueue<BoardPath> queue, HashMap<Integer,VisitedEntry> visitedMap )
	{
		
		if ( finished )
		{
			return;
		}
		
//		if ( bp.depthLeft == 0 )
//		{
//			return;
//		}
		
		if ( bp.board.isFinished() )
		{
			System.out.println("alla boxar paa alla goals");
			solution = createSolutionFromVisitedEntries( bp.lastVisitedEntry );
			
			reportSolution( solution );
			return; 
		}
		
		for ( Move move : bp.board.getLegalMoves( bp.board.getPlayer() , naiveMoveRule) )
		{

			BoardImplFast newBoard = bp.board.cloneThis();
			newBoard.doMovePlayer( move.getDirectionToThis() );

					
			int newBoardHashCode = newBoard.hashCode();
			
//			System.out.println(newBoardHashCode);
			
			if ( !visitedMap.containsKey( newBoard.hashCode() ) )
			{
				
//				newBoard.printBoard();

				VisitedEntry newEntry = new VisitedEntry( newBoardHashCode, move.getDirectionToThis(), bp.lastVisitedEntry );
				
				visitedMap.put( newBoard.hashCode(), newEntry );

				iterationCounter++;
				
//				BoardPath newBP = new BoardPath( newBoard, null, 
//						bp.depth-1, bp.beginDirection, bp.boxManhattanDistanceMatrix, newEntry, distanceCache );
				BoardPath newBP = new BoardPath( newBoard, null, 
						bp.depth-1, bp.beginDirection, newEntry, distanceCache );
				
				
				queue.add( newBP );
			}
		}
	}
	
	private String createSolutionFromVisitedEntries( VisitedEntry lastEntry )
	{
		StringBuilder sb = new StringBuilder();

		while ( lastEntry != null )
		{
			sb.append( lastEntry.direction.toString() );
			
//			System.out.println( entry.direction.toString() );
			
			lastEntry = lastEntry.lastEntryPointer;
		}
		
		sb.reverse();
		
		return sb.toString();
		
	}

}
